package com.cuz.daileetcode;

import java.util.Arrays;
import java.util.List;

/**
 * @author cuzz
 * @version 1.0
 * @description: 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * <p>
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 * 2
 * 3 4
 * 6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 * <p>
 * 输入：triangle = [[-10]]
 * 输出：-10
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -104 <= triangle[i][j] <= 104
 *  
 * <p>
 * 进阶：
 * <p>
 * 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/triangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 21:19 2021/9/20
 **/
public class Day3 {

    public static class Solution1 {
        public static int solute(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0) {
                return 0;
            }
            if (triangle.size()==1){
                return triangle.get(0).get(0);
            }
            int[] dp = new int[triangle.size()];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = triangle.get(0).get(0);
            int res =Integer.MAX_VALUE;
            for (int row = 1; row < triangle.size(); row++) {
                List<Integer> tmp = triangle.get(row);
                int[] ints = Arrays.copyOf(dp, dp.length);
                for (int col = 0; col < tmp.size(); col++) {
                    int min = Math.min(ints[Math.max(col - 1, 0)], ints[col]);
                    dp[col] =tmp.get(col)+ min;
                    if (row == triangle.size() - 1) {
                        res=Math.min(res, dp[col]);
                    }
                }
            }
            return res;
        }
        //[[2],[3,4],[6,5,7],[4,1,8,3]]
        public static void main(String[] args) {
            List<List<Integer>> lists = Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3));
            System.out.println(solute(lists));
        }
    }


}
